#pragma once

#include "red_black_tree.h"
#include "pair.h"
#include "reverse_iterator.h"

namespace self
{
	template <class key, class value>
	class map
	{
	public:
		struct KeyOfMap
		{
			key operator()(const pair<key, value>& kv)
			{
				return kv.first;
			}
		};
		typedef redBlackTreeNode<pair<key, value>> Node;
		typedef typename redBlackTree<key, pair<key, value>,KeyOfMap>::iterator iterator;
		typedef typename redBlackTree<key, pair<key, value>, KeyOfMap>::const_iterator const_iterator;
		typedef typename redBlackTree<key, pair<key, value>, KeyOfMap>::reverse_iterator reverse_iterator;
		typedef typename redBlackTree<key, pair<key, value>, KeyOfMap>::const_reverse_iterator const_reverse_iterator;

		iterator begin()
		{
			return _rb.begin();
		}

		iterator end()
		{
			return _rb.end();
		}

		const_iterator begin() const
		{
			return _rb.begin();
		}

		const_iterator end() const
		{
			return _rb.end();
		}

		reverse_iterator rbegin()
		{
			return _rb.rbegin();
		}

		reverse_iterator rend()
		{
			return _rb.rend();
		}

		const_reverse_iterator rbegin() const
		{
			return _rb.rbegin();
		}

		const_reverse_iterator rend() const
		{
			return _rb.rend();
		}

		map()
		{}

		template<class InputIterator>
		map(InputIterator first, InputIterator end)
		{
			while (first != end)
			{
				insert(*first);
				++first;
			}
		}

		map(const map<key,value>& m)
		{
			map<key,value> tmp(m.begin(), m.end());
			swap(tmp);
		}

		map& operator=(map m)
		{
			swap(m);
			return *this;
		}
		
		void swap(map<key,value>& tmp)
		{
			Node* root = _rb.get_root();
			_rb.get_root() = tmp._rb.get_root();
			tmp._rb.get_root() = root;
		}

		pair<iterator,bool> insert(const pair<key, value>& kv)
		{
			return _rb.insert(kv);
		}

		iterator find(const key& k)
		{
			auto it = begin();
			while (it != end())
			{
				if (it->first == k)
				{
					return it;
				}
				++it;
			}
			return end();
		}

		value& operator[](const key& k)
		{
			pair<iterator, bool> p(_rb.insert(make_pair(k,value())));
			return p.first->second;
		}

		size_t size()
		{
			return _rb.size();
		}

		void clear()
		{
			_rb.clear(_rb.get_root());
			_rb.get_root() = nullptr;
		}

		bool empty()
		{
			return _rb.get_root() == nullptr;
		}
	protected:
		redBlackTree<key, pair<key,value>,KeyOfMap> _rb;
	};

	template <class key, class value>
	class multimap : public map<key, value>
	{
		typedef typename map<key, value>::iterator iterator;
	public:
		pair<iterator, bool> insert(const pair<key, value>& kv)
		{
			return this->_rb.multiinsert(kv);
		}

		value& operator[](const key& k)
		{
			pair<iterator, bool> p(this->_rb.multiinsert(make_pair(k, value())));
			return p.first->second;
		}
	};
}


